package Linklist;

import java.util.ArrayList;

/**
 * @Classname JZ36二叉搜索树与双向链表
 * @Description TODO
 * @Date 2023/2/11 14:25
 * @Created by xjl
 */
public class JZ36二叉搜索树与双向链表 {

    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    Node tail, head;

    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        dfs(root);
        head.left = tail;
        tail.right = head;
        return head;
    }

    void dfs(Node cur) {
        if (cur == null) {
            return;
        }
        dfs(cur.left);
        if (tail != null) {
            tail.right = cur;
        } else {
            // 访问首个节点 head=curr
            head = cur;
        }
        cur.left = tail;
        tail = cur;
        dfs(cur.right);
    }

    ArrayList<Node> list = new ArrayList();

    public Node treeToDoublyList2(Node root) {
        if (root == null) {
            return root;
        }
        dfs(root);
        // 中序遍历，创建list先存起来，最后遍历list串起来
        for (int i = 0; i < list.size() - 1; i++) {
            Node tail = list.get(i);
            Node cur = list.get(i + 1);
            tail.right = cur;
            cur.left = tail;
        }
        Node head = list.get(0);
        Node hail = list.get(list.size() - 1);
        head.left = hail;
        hail.right = head;
        return head;
    }

    private void dfs2(Node root) {
        if (root == null) {
            return;
        }
        dfs2(root.left);
        list.add(root);
        dfs2(root.right);
    }
}
